package com.code.leetcode.center50;

import com.code.leetcode.utils.TreeNode;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/27 12:48
 */
public class The124_dfs {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(dfs(node.left), 0);
        int right = Math.max(dfs(node.right), 0);
        int sum = node.val + left + right;
        max = Math.max(sum, max);
        return node.val + Math.max(left, right);
    }
}
